struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

    struct ListNode* cur1 = list1,*cur2 = list2;
    struct ListNode* list3tail = NULL,*list3phead = NULL;

    if(cur1 == NULL)
    {
        list3phead = cur2;
        return list3phead;
    }
    if(cur2 == NULL)
    {
        list3phead = cur1;
        return list3phead;
    }
    while(cur1 && cur2)
    {
        if(cur1->val <= cur2->val)
        {
            if(list3tail == NULL)
            {
                list3tail = cur1;
                list3phead = cur1;
            }
            else
            {
                list3tail->next = cur1;
                list3tail = list3tail->next;
            }
            cur1 = cur1->next;
        }
        else
        {
            if(list3tail == NULL)
            {
                list3tail = cur2;
                list3phead = cur2;
            }
            else
            {
                list3tail->next = cur2;
                list3tail = list3tail->next;
            }
            cur2 = cur2->next;
        }
    }
    if(cur1)
        list3tail->next = cur1;
    if(cur2)
        list3tail->next = cur2;

    return list3phead;
}